#leetcode题目152：乘积最大子数组
#难度：中等
#时间复杂度：O(n)
#空间复杂度：O(1)

from typing import List

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n = len(nums)
        
        # dp[i][0] 表示以 nums[i] 结尾的最大乘积
        # dp[i][1] 表示以 nums[i] 结尾的最小乘积
        dp = [[0, 0] for _ in range(n)]
        
        # 初始化：每个元素本身作为子数组
        for i in range(n):
            dp[i][0] = nums[i]  # 最大乘积
            dp[i][1] = nums[i]  # 最小乘积
        
        # 动态规划计算
        for j in range(1, n):
            num = nums[j]
            
            # 计算以 nums[j] 结尾的最大乘积
            # 考虑三种情况：
            # 1. 只选择当前数字
            # 2. 当前数字 × 前一个位置的最大乘积
            # 3. 当前数字 × 前一个位置的最小乘积（负数情况）
            max_val = max(
                num,                           # 只选择当前数字
                dp[j-1][0] * num,             # 当前数字 × 前一个最大乘积
                dp[j-1][1] * num              # 当前数字 × 前一个最小乘积
            )
            
            # 计算以 nums[j] 结尾的最小乘积
            min_val = min(
                num,                           # 只选择当前数字
                dp[j-1][0] * num,             # 当前数字 × 前一个最大乘积
                dp[j-1][1] * num              # 当前数字 × 前一个最小乘积
            )
            
            dp[j][0] = max_val
            dp[j][1] = min_val
        
        # 找到所有位置的最大乘积中的最大值
        result = dp[0][0]
        for i in range(1, n):
            result = max(result, dp[i][0])
        
        return result


#测试数据
nums = [2,3,-2,4]
#预期输出：6,最大乘积子数组是[2,3]
solution = Solution()
print(solution.maxProduct(nums))

nums = [-2,0,-1]
#预期输出：0,最大乘积子数组是[0],  不能是2，因为[-2,-1]不是子数组
solution = Solution()
print(solution.maxProduct(nums))